package com.future;

/**
 * Description:
 *
 * @author weiruibai.vendor
 * Date: 2021/9/18 16:51
 */
public class Solution_665 {

    public static void main(String[] args) {

        Solution_665 solution03 = new Solution_665();
        int maxLength = 12;
        int maxValue = 10;
        int[] nums = CommonUtil.generateRandomList(maxLength, maxValue);
        nums = new int[]{3, 4, 2, 6};
        //nums = new int[]{2, 4, 5, 2, 3};
        //nums = new int[]{4, 2, 3};
        //nums = new int[]{1, 2, 3, 1};
        System.out.println(solution03.checkPossibility(nums));

    }

    /**
     * 给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
     * <p>
     * 我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/non-decreasing-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public boolean checkPossibility_v2(int[] nums) {
        boolean bb = true;
        int N = nums.length;
        int pre = 0;
        for (int i = 0; i < N - 1; i++) {
            if (nums[i] >= nums[i + 1]) {
                if (!bb || (nums[pre] > nums[i + 1] && pre != 0 && i + 1 != N - 1)) {
                    return false;
                }
                bb = false;
            } else {
                pre = i;
            }
        }
        return true;
    }

    /**
     * 思路：
     * example1:{3, 4, 2, 6}->{3,2,2,6}(不满足，继续)->{3, 4, 4, 6}(满足，返回)
     * example2:{3, 4, 2, 3}->{3,2,2,3}(不满足，继续)->{3, 4, 4, 3}(不满足，结束)
     *
     * @param nums
     * @return
     */
    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                // 修改
                nums[i] = y;
                // 遍历查看是否符合小到大
                if (isSorted(nums)) {
                    return true;
                }
                nums[i] = x; // 复原
                nums[i + 1] = x;
                return isSorted(nums);
            }
        }
        return true;
    }

    public boolean isSorted(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; ++i) {
            if (nums[i - 1] > nums[i]) {
                return false;
            }
        }
        return true;
    }

}
